1. Field of the Invention
The invention relates to a Chien search method in Reed-Solomon decoding, more particularly to a Chien search method in Reed-Solomon decoding, which can reduce program flow branching so as to enhance efficiency, and to a machine-readable recording medium including a plurality of instructions for executing the method.
2. Description of the Related Art
In recent years, demand for reliable signal transmission with respect to products ranging from consumer electronic products to communications electronic products has increased considerably. Therefore, error detection and correction mechanisms are becoming more and more important. During the process of digital communication, to ensure the accuracy of source data to be transmitted, a transmitting end generally will append redundant data to the source data, so that the receiving end can perform error correction based on the redundant data. The Reed-Solomon code is a widely used correction code. Since the Reed-Solomon code has a good correction capability with respect to errors generated in transmission channels, it has become a very popular channel coding scheme, and is now a widely used error correction code in satellite communication systems, digital television systems, various digital audiovisual recording media, etc.
Even though the Reed-Solomon code has excellent performance in error correction, the amount of computations required for decoding is huge. Consequently, hardware is often used for calculation and processing. If the Reed-Solomon code is executed in a processor in the form of program decoding, the decoding speed will inevitably become extremely slow due to the huge computation amount. Therefore, in some applications of communications devices with software-defined operations (such as software defined radio (SDR)), accelerating the program decoding speed of the Reed-Solomon code has become an important subject of research.
Referring to FIG. 1, an existing Reed-Solomon decoding procedure can be divided into four stages, which are, as shown, a stage 11 of calculating syndromes, a stage 12 of calculating error location polynomials, a stage 13 of executing a Chien search, and a stage 14 of calculating error values. In this Reed-Solomon decoding procedure, about 40% of the computation amount is concentrated on the Chien search at stage 13. If the processing time for executing the Chien search can be effectively reduced, the decoding speed of the Reed-Solomon code can be successfully accelerated.
Referring to FIG. 2, a conventional Chien search method in Reed-Solomon decoding includes the following steps. In step 21, a location index j and a symbol index i are initialized, i.e., j=0, and i=0. In step 22, an error evaluation value Λ(αi) is calculated. In step 23, a decision is performed to determine if the error evaluation value Λ(αi) is equal to 0. If yes, this indicates that an error occurs in a symbol at the ith position, and step 24 is carried out to perform the necessary processing. Otherwise, the flow goes to the processing in step 26. In steps 24 and 25, the current symbol index i is first stored in an error location array, Location[j]=1, followed by incrementing the location index, j=j+1. In steps 26-28, a decision is performed to determine if the Chien search has been completed, i.e., determining if i=n−1. If yes, the Chien search is ended. Otherwise, the symbol index i is incremented, i=i+1, and the aforesaid steps 22-26 are repeated. In steps 24-25, n represents a total number of symbols of a Reed-Solomon block code that was received.
The determination processing in step 23 of the aforesaid conventional method will generate program flow branching. That is, one operation (step 24) will be executed when Λ(αi)=0, and another operation (step 26) will be executed when Λ(αi)≠0. Branching will result in disordered execution of a processor, causing a reset of internal instructions and data of a pipeline of the processor, thereby affecting the overall efficiency of the processor adversely.
Other conventional Chien search schemes in the Reed-Solomon code, such as those disclosed in U.S. Pat. No. 6,263,470 and U.S. Pat. No. 6,360,348, are primarily concerned with the acceleration of the computation of the Chien search process using look-up tables, and are silent on the problem of program flow branching associated with the Chien search process.
Therefore, there is a need for a solution to reduce the program flow branching in the aforesaid conventional method, so that the processing time of the Chien search can be further reduced to thereby increase the decoding speed of the Reed-Solomon code.